package com.lw.leetcode.arr.b;

/**
 * 934. 最短的桥
 *
 * @Author liw
 * @Date 2021/9/1 22:23
 * @Version 1.0
 */
public class ShortestBridge {

    public static void main(String[] args) {
        ShortestBridge test = new ShortestBridge();
//        int[][] arr = {{1,0}, {0,1}};
//        int[][] arr = {{0,1,0},{0,0,0},{0,0,1}};
//        int[][] arr = {
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
//                {0, 1, 1, 1, 1, 0, 0, 1, 0, 0},
//                {1, 1, 1, 1, 1, 1, 1, 1, 1, 0},
//                {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
//                {1, 0, 1, 1, 1, 1, 1, 1, 1, 0},
//                {1, 1, 0, 1, 1, 1, 1, 1, 1, 1}
//        };
        int[][] arr =
                {
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0}};
        int i = test.shortestBridge(arr);
        System.out.println(i);
    }

    private int[][] grid;
    private int a;
    private int b;

    private int min = Integer.MAX_VALUE;

    public int shortestBridge(int[][] grid) {
        this.grid = grid;
        this.a = grid.length;
        this.b = grid[0].length;
        this.min = a + b;
        one:
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (grid[i][j] == 1) {
                    find(i, j);
                    break one;
                }
            }
        }
        for (int i = a - 1; i >= 0; i--) {
            for (int j = b - 1; j >= 0; j--) {
                if (grid[i][j] == -1) {
                    find(i + 1, j, 1);
                    find(i - 1, j, 1);
                    find(i, j + 1, 1);
                    find(i, j - 1, 1);
                }
            }
        }
        return min - 1;
    }

    private void find(int x, int y, int s) {
        if (x < 0 || x == a || y < 0 || y == b || s >= min || grid[x][y] == -1) {
            return;
        }
        if (grid[x][y] == 1) {
            min = Math.min(min, s);
            return;
        }
        if (grid[x][y] == 0 || grid[x][y] > s + 1) {
            grid[x][y] = s + 1;
            find(x + 1, y, s + 1);
            find(x - 1, y, s + 1);
            find(x, y + 1, s + 1);
            find(x, y - 1, s + 1);
        }
    }

    private void find(int x, int y) {
        if (x < 0 || x == a || y < 0 || y == b) {
            return;
        }
        if (grid[x][y] == 1) {
            grid[x][y] = -1;
            find(x + 1, y);
            find(x - 1, y);
            find(x, y + 1);
            find(x, y - 1);
        }
    }

}
